package com.le.tester.webpage.masterCode.sortdemo;

import com.google.common.collect.ImmutableList;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 描述：二分查找
 */
public class BinarySearchDemo {
    public void testBinarySearch() {
        List<SortDemo> sorts = ImmutableList.of(
                new SortDemo("300"),
                new SortDemo("50"),
                new SortDemo("200"),
                new SortDemo("220"));
        //sort方法第一个传入的需要数组
        SortDemo[] sortDemos = new SortDemo[sorts.size()];
        sorts.toArray(sortDemos);
        System.out.println("排序之前：" + Arrays.toString(sortDemos));
        Arrays.sort(sortDemos, new NormalComparator());
        System.out.println("排序之后：" + Arrays.toString(sortDemos));

        //二分查找,使用之前请先进行排序，返回的是这个值在数组中的下标
        int index = Arrays.binarySearch(sortDemos, new SortDemo("200"), new NormalComparator());
        if (index < 0) {
            throw new RuntimeException("没有找到 200");
        }
        System.out.println("二分搜索的结果：" + sortDemos[index] + " 下标为：" + index);
    }

    public static <T> int f1(T[] a, int from, int to, Comparator<? super T> c, T key) {
        if (c == null) {
            return -1;
        }
        //这里不使用默认的比较器
        int low = from;
        int high = to - 1;

        //开始的位置应该小于终点的位置,这边直接的使用while
        while (low <= high) {
            int mid = (low = high) >>> 1;
            T midValue = a[mid];

            //直接对半的比较，看是坐落在左边还是右边,就表示你要先进行排序了
            int compare = c.compare(midValue, key);
            if (compare < 0) {
                low = mid + 1;
            } else if (compare > 0) {
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return -(low + 1);
    }

    public static void main(String[] args) {
        BinarySearchDemo binarySearchDemo = new BinarySearchDemo();
        binarySearchDemo.testBinarySearch();
    }
}
